package sivan.letcode;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;

public class LRUCache<K, V> {

    private final int CacheCapacity;
    private final HashMap<K, CacheNode<K>> caches;
    private CacheNode<K> first;
    private CacheNode<K> last;

    public LRUCache(int size) {
        this.CacheCapacity = size;
        caches = new HashMap<>(size);
    }

    public void put(K k, V v) {
        CacheNode<K> node = caches.get(k);
        if (node == null) {
            if (caches.size() >= CacheCapacity) {
                caches.remove(last.key);
                removeLast();
            }
            node = new CacheNode<>();
            node.key = k;
        }
        node.value = v;
        moveToFirst(node);
        caches.put(k, node);
    }

    public Object get(K k) {
        CacheNode<K> node = caches.get(k);
        if (node == null) {
            return null;
        }
        moveToFirst(node);
        return node.value;
    }


    private void moveToFirst(CacheNode<K> node) {
        if (first == null || last == null) {
            first = last = node;
            return;
        }

        if (node == first) {
            return;
        }

        if (node.next != null) {
            node.next.pre = node.pre;
            node.pre.next = node.next;
        }

        if (node == last) {
            last = last.pre;
        }

        node.next = first;
        first.pre = node;
        first = node;
        first.pre = null;
    }

    private void removeLast() {
        if (last != null) {
            last.pre.next = null;
            last = last.pre;
        }
    }


    static class CacheNode<k> {
        CacheNode<k> pre;
        CacheNode<k> next;
        k key;
        Object value;

        public CacheNode() {

        }
    }

    static class Node {
        int value;
        Node next;

        public Node(int value, Node d) {
            this.value = value;
            this.next = d;
        }
    }

    public static void main(String[] args) {
        Node a = new Node(3, null);
        Node b = new Node(2, a);
        Node c = new Node(1, b);
        Node head = list(c);
        System.out.println(head);
    }

    public static Node list(Node node) {
        if (node == null) {
            return null;
        }
        List<Node> list = new ArrayList<>();
        while (node != null) {
            list.add(node);
            node = node.next;
        }

        list.get(0).next = null;
        Node head = null;
        for (int i = list.size() - 1; i >= 0; i--) {
            if (head == null) {
                head = list.get(i);
                node = head;
            } else {
                node.next = list.get(i);
                node = node.next;
            }
        }
        return head;
    }
}
